#!/usr/bin/python
import sys
import random
from datetime import datetime

class Title:
       def __init__(self,name="",id=0):
               self.name=name.rstrip('\n')
               self.id=id
               self.prefixes=make_prefixes(self.name,self.id)
               self.suffixes=make_suffixes(self.name,self.id)
               self.next=[]
               self.prev=[]
               self.hasNext=0
               self.hasPrev=0
	       self.graphNo=0

       def Print(self):
               print self.name

       def addNext(self,id):
               self.next.append(id)

       def addPrev(self,id):
               self.prev.append(id)

       def allNext(self,idSet):
               ids=[]
               if len(self.next) == 0:
                       return ids
               for id in self.next:
                       if id not in idSet:
                               ids.append(id)
               return ids

################################
def readFile(filename):
	infile = open(filename,"r") 
	mDict={}
	counter=0
	while infile:
	       line=infile.readline()
	       length=len(line)
	       if length==0:
	               break
	       movie=Title(line,counter)
	       mDict[counter]=movie
	       counter=counter+1
	return mDict


def traverse(movieChain,movie,idSet):
	global verbose
	global longestMovieChain
	newIdSet=idSet.copy()
        newIdSet.add(movie.id)
        nextMovieIds=movie.allNext(newIdSet)
	random.shuffle(nextMovieIds)
	for movieId in nextMovieIds:
	       global iterations
	       iterations=iterations+1
               nextMovie=moviesDict[movieId]
               newMovieChain=movieChain[:]
               newMovieChain.append(nextMovie.name) 
               if len(newMovieChain)>len(longestMovieChain):
			global vverbose
			if vverbose:
				print longestMovieChain
				print "____running____Longest Chain("+str(len(longestMovieChain))+")" 
                        longestMovieChain=newMovieChain[:]
	       global maxiterations
	       if iterations < maxiterations:
			traverse(newMovieChain,nextMovie,newIdSet) 
	return 0

def runTraversal(mDict):
	movieValues=mDict.values()
	random.shuffle(movieValues)
	global longestMovieChain
	longestMovieChain=[movieValues[0].name]
	totalmovies=len(movieValues)
	for index,movie in enumerate(movieValues):
		global iterations
		global starts
		if index>=starts:
			break
		iterations=0
		if verbose:
        		print "("+str(index+1)+"/"+str(len(mDict))+"):"+"++++++++++++"+movie.name+"++++++++++++++++++"
	        try:
	                traverse([movie.name],movie,set([]))
	        except (KeyboardInterrupt, SystemExit):
			print longestMovieChain
	                print "++++quit++++Longest Chain("+str(len(longestMovieChain))+")"
			print "iterations="+str(iterations)
	                exit() 
	return 0

def make_prefixes(name,id):
       words=name.split()
       p=[]
       for i in range(0,len(words)):
               prefix=" ".join(words[:i])
               p.append(prefix)
               if prefix in prefixes:
                        prefixes[prefix].append(id)
               else:
                        prefixes[prefix]=[id]
       return set(p)

def make_suffixes(name,id):
       words=name.split()
       s=[]
       for i in range(0,len(words)):
               suffix=" ".join(words[i:])      
               s.append(suffix)
               if suffix in suffixes:
                        suffixes[suffix].append(id)
               else:
                        suffixes[suffix]=[id]
       return set(s)

def makePrefixSuffix(prefixes,suffixes): 
	temp=suffixes.keys()
	for key in temp:
	        if key not in prefixes:
	                del suffixes[key]
	temp=prefixes.keys()
	for key in temp:
	        if key not in suffixes:
	                del prefixes[key]
	global verbose
	if verbose:
		print "==============Done matching prefixes and suffixes==============="
	for key,list in suffixes.iteritems():
	        for id in list:
	                moviesDict[id].next.extend(prefixes[key])
	                moviesDict[id].hasNext=1
	for key,list in prefixes.iteritems():
	        for id in list:
	                moviesDict[id].prev.extend(suffixes[key])
	                moviesDict[id].hasPrev=1
	if verbose:
		print "===========Done adding prev and next==========="
	for key in moviesDict:
	       movie=moviesDict[key]
	       if movie.hasNext and movie.hasPrev:
	               cleanMoviesDict[movie.id]=movie
	       elif movie.hasNext:
	               headMoviesDict[movie.id]=movie
	       elif movie.hasPrev:
	               tailMoviesDict[movie.id]=movie
	       else:
	             exMoviesDict[movie.id]=movie 

def make_dot_file(mDict): 
	print "digraph movies {" 
	for id,movie in mDict.iteritems():
        	for id2 in movie.next:
                	print '"'+movie.name+'"->"'+moviesDict[id2].name+'"'
	print "}" 

def countGraph(mDict):
	print "Counting Graph"
	global moviesDict
	movielist=mDict.keys()
	readylist=[]
	readylist.append(movielist[0])
	graphNo=0
	for mid in movielist:
		readylist=[]
	        readylist.append(mid) 
		if not moviesDict[mid].graphNo:
			graphNo=graphNo+1
		for id in readylist:
			if not moviesDict[id].graphNo:
				moviesDict[id].graphNo=graphNo
			newids=moviesDict[id].next
			for id2 in newids:	
				if not moviesDict[id2].graphNo:
					readylist.append(id2)
			newids=moviesDict[id].prev
                        for id2 in newids:
                                if not moviesDict[id2].graphNo:
                                        readylist.append(id2) 
	graphDict={}
		
	for id,movie in moviesDict.iteritems():
		if movie.graphNo in graphDict:
			graphDict[movie.graphNo].add(id)
		else:
			graphDict[movie.graphNo]=set([id])
		if verbose:
			print "countgraph:"+movie.name+";graphNo="+str(movie.graphNo) 	

	largestGraph=1
	for graphNo,movielist in graphDict.iteritems():
		if len(movielist)>len(graphDict[largestGraph]) and graphNo>0:
			largestGraph=graphNo
		if len(movielist) > 4:
			print str(graphNo)+" length= "+str(len(movielist))

	print "largest graph is graphNo="+str(largestGraph)+", with "+str(len(graphDict[largestGraph]))+" members"
	largestGraphDict={}
	for id in graphDict[largestGraph]:
		largestGraphDict[id]=moviesDict[id]
	return largestGraphDict
################################

verbose=0
vverbose=0
makeDot=0
trav=0 
graph=0
starts=10
maxiterations=20000
filename = "MOVIES.LST"

starttime=datetime.now()

if "-v" in sys.argv:
        verbose=1
if "-vv" in sys.argv:
	vverbose=1
	verbose=1
if "-d" in sys.argv:
        makeDot=1
if "-t" in sys.argv:
        trav=1
if "-g" in sys.argv:
	graph=1
if "-f" in sys.argv:
	i=sys.argv.index("-f")
	filename=sys.argv[i+1] 
if "-i" in sys.argv:
	i=sys.argv.index("-i")
	maxiterations=int(sys.argv[i+1])
if "-s" in sys.argv:
        i=sys.argv.index("-s")
        starts=int(sys.argv[i+1])

moviesDict={}
cleanMoviesDict={} 
headMoviesDict={}
tailMoviesDict={}
exMoviesDict={}

prefixes={}
suffixes={}

iterations=0
longestMovieChain=[]

moviesDict=readFile(filename)

if verbose:
	print "=========Done reading file================"
makePrefixSuffix(prefixes,suffixes)
if verbose:
	print "=====PREPROCESSING DONE======"
	print "number of movies="+str(len(moviesDict))
	print "number of linked movies="+str(len(cleanMoviesDict))
	print "number of head only movies="+str(len(headMoviesDict))
	print "number of tail only movies="+str(len(tailMoviesDict))
	print "number of excluded movies="+str(len(exMoviesDict))

################################################
largestGraphDict={}
if graph:
	largestGraphDict=countGraph(cleanMoviesDict)	

if makeDot:
	make_dot_file(headMoviesDict)

if trav:
	runTraversal(headMoviesDict)

################################################
endtime=datetime.now()
difftime=endtime-starttime
print longestMovieChain
print "=====FINISHED======Longest Chain("+str(len(longestMovieChain))+")"
print "runtime="+str(difftime)
exit()
